package q940_distinctSubseqII;

import java.util.Arrays;

public class Solution_1 {
    /*
    不同的子序列
    一个比较好的想法
    https://leetcode.cn/problems/distinct-subsequences-ii/solution/by-da-yu-bt-jy18/
    首先是从最基本的做法开始，每次考虑
    用 f[i] 表示以 s[i] 为最后一个字符的子序列的数目。
    如果子序列中只有 s[i] 这一个字符，那么有一种方案；
    如果子序列中至少有两个字符，那么我们可以枚举倒数第二个字符来进行状态转移。
    容易想到的是：倒数第二个字符可以选择 s[0],s[1],⋯,s[i−1] 中的某一个，
    这样就可以得到如下的状态转移方程：
    f[i]=f[0]+f[1]+⋯f[i−1]
     */
    public int distinctSubseqII(String s) {
        final int MOD = 1000000007;
        int[] last = new int[26];
        Arrays.fill(last, -1);

        int n = s.length();
        int[] dp = new int[n];
        Arrays.fill(dp, 1);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 26; j++) {
                if (last[j] != -1) dp[i] = (dp[i] + dp[last[j]]) % MOD;
            }
            last[s.charAt(i) - 'a'] = i;
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (last[i] != -1) ans = (ans + dp[last[i]]) % MOD;
        }
        return ans;

    }

}
